package com.leet.code.simple_array;

import java.util.HashMap;
import java.util.Map;

/**
 * @description:    1394.找出数组中的幸运数
 * @author: WYG
 * @time: 2021/1/3 20:40
 */

public class FindLucky {

    //利用计数排序
    public int fast_findLucky(int[] arr) {
        int res = -1;
        //存放arr数组元素中每个元素出现的次数,元素出现的次数就是bucket数组对应下标的值
        int[] bucket = new int[501];
        for (int x : arr) {
            bucket[x]++;
        }
        //遍历bucket数组,下标与对应的数组值相等说明元素的值和出现次数相等,如果此时下标大于res,那么就赋值给res
        for (int i = 1; i < 501; i++) {
            if (bucket[i] == i && i > res) {
                res = i;
            }
        }
        return res;
    }

    public int findLucky(int[] arr) {
        int res = -1;
        //存放元素出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        //统计元素出现的次数
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
        }
        //遍历map,查找元素中的幸运数字,并将最大值赋值给res
        for (Map.Entry entry : map.entrySet()) {
            if ((entry.getKey() == entry.getValue()) && ((int) entry.getKey() > res)) {
                res = (int) entry.getKey();
            }
        }
        return res;
    }
}
